{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "p = 0x0800000000000011000000000000000000000000000000000000000000000001"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "l = 0x0800000000000010ffffffffffffffffb781126dcae7b2321e66a241adc64d2f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "def embedding_degree(p, l):\n",
    "    pp = 1\n",
    "    # TODO: try (l-1)/n\n",
    "    for i in range(1, 10**7):\n",
    "        pp *= p\n",
    "        pp %= l\n",
    "        if pp == 1:\n",
    "            return i\n",
    "        if i % 10**6 == 0:\n",
    "            print(i, pp)\n",
    "    return \"> N\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.618502788666131e+73"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(ℓ-1)/100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000000 1578306871819672483813147171655531803995321030976714780567501499271936894699\n",
      "2000000 1606712496998082715113643482710828122161979184924028104195925173172359847455\n",
      "3000000 1432592280107326262745754650815182094358089536333640591374264953315985641653\n",
      "4000000 1619747091821847920535899037397716332861452747163491677808735468629485206044\n",
      "5000000 398975072553706817943396627870660638624476176139529473762267749129551896587\n",
      "6000000 3257297284789235427779355010377513650244781788113949467967440395148285094789\n",
      "7000000 2075864992820472695981735667435876605864733562318852749859396594858790408100\n",
      "8000000 3034963322103916032347891039327850133818757400216732792182500913296186501492\n",
      "9000000 1480946314149908619442707550771106696562877433503946318227244424937788255653\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'> N'"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "embedding_degree(p, l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# BN(2, 254)\n",
    "embedding_degree(\n",
    "    16798108731015832284940804142231733909889187121439069848933715426072753864723,\n",
    "    16798108731015832284940804142231733909759579603404752749028378864165570215949)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
